package com.jerry.hm.datastructure.priorityqueue;

import com.jerry.hm.datastructure.queue.Queue;

/**
 * 无序数组实现优先级队列
 *
 * @author Jerry
 * @since 2024/10/5 9:51
 */
public class PriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] array;
    private int size;

    public PriorityQueue(int capacity) {
        array = new Priority[capacity];
    }

    /**
     * 向队尾插入元素
     *
     * @param e
     * @return
     */
    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        array[size++] = e;
        return true;
    }

    /**
     * 从队首移除元素
     *
     * @return
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        remove(max);
        size--;
        return e;
    }

    /**
     * 从队首获取元素
     *
     * @return
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        return (E) array[max];
    }

    /**
     * 队列是否空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 队列是否满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }

    /**
     * 返回优先级最高的索引
     *
     * @return
     */
    private int selectMax() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    /**
     * 移除指定索引的元素
     *
     * @param max
     */
    private void remove(int max) {
        if (max < size - 1) {
            System.arraycopy(array, max + 1, array, max, size - max - 1);
        }
        array[size - 1] = null;
    }
}
